package leetcode22

// 回溯算法
func generateParenthesis(n int) []string {
	var (
		ans []string = make([]string, 0)
	)
	backtrack(&ans, []int32{}, 0, 0, n)
	return ans
}

func backtrack(ans *[]string, cur []int32, open, close int, max int) {
	if len(cur) == max*2 {
		*ans = append(*ans, string(cur))
		return
	}

	if open < max {
		cur = append(cur, '(')
		backtrack(ans, cur, open+1, close, max)
		cur = cur[:len(cur)-1]
	}
	if close < open {
		cur = append(cur, ')')
		backtrack(ans, cur, open, close+1, max)
		cur = cur[:len(cur)-1]
	}
}
